Busqueda Informada y Exploracion

Hay una familia entera de algoritmos de BUSQUEDA-PRIMERO-MEJOR con funciones de evaluacion diferentes. Una componente clave de estos algoritmos es una funcion heuristica , denotada h(n): h(n) coste estimado del camino mas barato desde el nodo n a un nodo objetivo. Por ejemplo, en Rumania, podriamos estimar el coste del camino mas barato desde Arad a Bucarest con la distancia en linea recta desde Arad a Bucarest. Las funciones heuristicas son la forma mas comun de transmitir el conocimiento adicional del problema al algoritmo de busqueda. Estudiaremos heuristicas con mas profundidad en la Seccion. Por ahora, las consideraremos funciones arbitrarias especificas del problema, con una restriccion: si n es un nodo objetivo, entonces h(n) 0. El resto de esta seccion trata dos modos de usar la informacion heuristica para dirigir la busqueda.

Las funciones heuristicas son aquellas que se utilizan para evaluar la calidad de una solucion parcial o completa en un problema de busqueda. Estas funciones se utilizan en algoritmos de busqueda informada, como el A*.

los algoritmos de busqueda local son utiles para resolver problemas de optimizacion puros, en los cuales el objetivo es encontrar el mejor estado segun una funcion objetivo. Muchos problemas de optimizacion no encajan en el modelo «estandar» de busqueda. Por ejemplo, la naturaleza proporciona una funcion objetivo (idoneidad o salud reproductiva) que la evolucion Darwiniana intenta optimizar, pero no hay ningun «test objetivo» y ningun «coste de camino» para este problema. Para entender la busqueda local, encontraremos muy util considerar la forma o el paisaje del espacio de estados. El paisaje tiene «posicion» (definido por el estado) y «elevacion» (definido por el valor de la funcion de coste heuristica o funcion objetivo). Si la elevacion corresponde al costo, entonces el objetivo es encontrar el valle mas bajo (un minimo global); si la elevacion corresponde a una funcion objetivo, entonces el objetivo es encontrar el pico mas alto (un maximo global). (Puedes convertir uno en el otro solamente al insertar un signo menos.) Los algoritmos de busqueda local exploran este paisaje. Un algoritmo de busqueda local completo siempre encuentra un objetivo si existe; un algoritmo optimo siempre encuentran un minimo/maximo global. Busqueda de ascension de colinas Se muestra el algoritmo de busqueda de ascension de colinas. Es simplemente un bucle que continuamente se mueve en direccion del valor creciente, es decir, cuesta arriba. Termina cuando alcanza «un pico» en donde ningun vecino tiene un valor mas alto. El algoritmo no mantiene un arbol de busqueda, sino una estructura de datos del nodo actual que necesita solo el registro del estado y su valor de funcion objetivo. La ascension de colinas no mira delante mas alla de los vecinos inmediatos del estado actual. Se parece a lo que hacemos cuando tratamos de encontrar la cumbre del Everest en una niebla mientras sufrimos amnesia. Para ilustrar la ascension de colinas.

La busqueda local en espacios continuos es un tipo de algoritmo de busqueda local que se utiliza en problemas de optimizacion con variables continuas. En este tipo de problemas, se busca encontrar los valores optimos para las variables continuas que maximizan o minimizan una funcion objetivo.

Hasta ahora nos hemos centrado en agentes que usan algoritmos de busqueda offline. Ellos calculan una solucion completa antes de poner un pie en el mundo real, y luego ejecutan la solucion sin recurrir a su percepciones. En contraste, un agente de busqueda en linea (online) funciona intercalando el calculo y la accion: primero toma una accion, entonces observa el entorno y calcula la siguiente accion. La busqueda online es una buena idea en dominios dinamicos o semidinamicos (dominios donde hay una penalizacion por holgazanear y por utilizar demasiado tiempo para calcular). La busqueda online es una idea incluso mejor para dominios estocasticos. En general, una busqueda offline deberia presentar un plan de contingencia exponencialmente grande que considere todos los acontecimientos posibles, mientras que una busqueda online necesita solo considerar lo que realmente pasa. Por ejemplo, a un agente que juega al ajedrez se le aconseja que haga su primer movimiento mucho antes de que se haya resuelto el curso completo del juego. La busqueda online es una idea necesaria para un problema de exploracion, donde los estados y las acciones son desconocidos por el agente; un agente en este estado de ignorancia debe usar sus acciones como experimentos para determinar que hacer despues, y a partir de ahi debe intercalar el calculo y la accion. El ejemplo basico de busqueda online es un robot que se coloca en un edificio nuevo y lo debe explorar para construir un mapa, que puede utilizar para ir desde A a B. Los metodos para salir de laberintos (conocimiento requerido para aspirar a ser heroe de la Antiguedad) son tambien ejemplos de algoritmos de busqueda online. Sin embargo, la exploracion espacial no es la unica forma de la exploracion. Considere a un bebe recien nacido: tiene muchas acciones posibles, pero no sabe los resultados de ellas, y ha experimentado solo algunos de los estados posibles que puede alcanzar. El descubrimiento gradual del bebe de como trabaja el mundo es, en parte, un proceso de busqueda online.